package programmercarl.动态规划.C23;

class Solution1 {
    public int coinChange(int[] coins, int amount) {

        //最少数量
        int[] dp = new int[amount + 1];
        //初始化
        dp[0] = 0;//凑成为0的target需要的金币数量
        //完全背包，组合问题
        for (int i = 0; i < coins.length; i++) {
            for (int j = coins[i]; j <= amount; j++) {
                dp[j] = Math.max(dp[j], dp[j - coins[i]] + 1);
            }
        }
        return dp[amount]==Integer.MAX_VALUE?-1:dp[amount];
    }

    public static void main(String[] args) {
        Solution1 solution = new Solution1();
        int i = solution.coinChange(new int[]{1, 2, 5}, 11);
        System.out.print(i);
    }
}